from typing import List


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        if not triangle:
            return 0
        dp = [0] * len(triangle)
        dp[0] = triangle[0][0]
        for i in range(1, len(triangle)):
            # min(左边路径,右边路径)　+ 自己的值
            tmp = dp.copy()
            for j in range(i+1):
                if j == 0:
                    dp[j] = tmp[0] + triangle[i][j]
                elif j == i:
                    dp[j] = tmp[j-1] + triangle[i][j]
                else:
                    dp[j] = min(tmp[j-1], tmp[j]) + triangle[i][j]

        return min(dp)


if __name__ == "__main__":
    triangle = [
        [2],
        [3, 4],
        [6, 5, 7],
        [4, 1, 8, 3]
    ]  # 11
    res = Solution().minimumTotal(triangle)
    print(res)
